﻿using System;
using System.Collections.Generic;
using System.Text;


//无向图邻接表
public class GraphAdjList<T> : IGraph<T>
{
    //邻接表数组
    private VexNode<T>[] adjList;
    private int[] visited;
    public VexNode<T> this[int index]
    {
        get { return adjList[index]; }
        set { adjList[index] = value; }
    }

    public GraphAdjList(GraphNode<T>[] nodes)
    {
        adjList = new VexNode<T>[nodes.Length];
        for (int i = 0; i < nodes.Length; i++)
        {
            adjList[i].Data = nodes[i];
            adjList[i].FirstAdj = null;
        }

        visited = new int[adjList.Length];
        for (int i = 0; i < visited.Length; i++)
        {
            visited[i] = 0;
        }
    }

    public void DelEdge(GraphNode<T> v1, GraphNode<T> v2)
    {
        //v1或v2不是图的顶点
        if (!IsNode(v1) || !IsNode(v2))
        {
            Console.WriteLine("Node is not belong to Graph!");
            return;
        }

        if (IsEdge(v1, v2))
        {
            AdjListNode<T> p = adjList[GetIndex(v1)].FirstAdj;
            AdjListNode<T> pre = null;
            while (p != null)
            {
                if (p.Adjvex != GetIndex(v2))
                {
                    pre = p;
                    p = p.Next;
                }
            }

            pre.Next = p.Next;

            p = adjList[GetIndex(v2)].FirstAdj;
            pre = null;

            while (p != null)
            {
                if (p.Adjvex != GetIndex(v1))
                {
                    pre = p;
                    p = p.Next;
                }
            }
            pre.Next = p.Next;
        }
    }

    // 获取顶点的数量
    public int GetNumOfVertex()
    {
        return adjList.Length;
    }

    // 获取边的数量
    public int GetNumOfEdge()
    {
        int i = 0;
        foreach (VexNode<T> nd in adjList)
        {
            AdjListNode<T> p = nd.FirstAdj;
            while (p != null)
            {
                ++i;
                p = p.Next;
            }
        }

        return i / 2;
    }

    // 判断 v 是否是图的顶点
    public bool IsNode(GraphNode<T> v)
    {
        foreach (VexNode<T> nd in adjList)
        {
            if (v.Equals(nd.Data))
            {
                return true;
            }
        }
        return false;
    }

    // 获取顶点v在邻接表数组中的索引
    public int GetIndex(GraphNode<T> v)
    {
        int i = -1;
        for (i = 0; i < adjList.Length; i++)
        {
            if (adjList[i].Data.Equals(v))
            {
                return i;
            }
        }
        return -1;
    }

    public bool IsEdge(GraphNode<T> v1, GraphNode<T> v2)
    {
        //v1或v2不是图的顶点
        if (!IsNode(v1) || !IsNode(v2))
        {
            Console.WriteLine("Node is not belong to Graph!");
            return false;
        }

        AdjListNode<T> p = adjList[GetIndex(v1)].FirstAdj;
        while (p != null)
        {
            if (p.Adjvex == GetIndex(v2))
            {
                return true;
            }
            p = p.Next;
        }
        return false;
    }

    public void SetEdge(GraphNode<T> v1, GraphNode<T> v2, int v)
    {
        // v1 v2 不是图的顶点 或者v1v2存在边
        if (!IsNode(v1) || !IsNode(v2) || IsEdge(v1, v2))
        {
            Console.WriteLine("Node is not belong to graph");
            return;
        }

        if (v != 1)
        {
            Console.WriteLine("Weight is not right");
            return;
        }

        AdjListNode<T> p = new AdjListNode<T>(GetIndex(v2));
        if (adjList[GetIndex(v1)].FirstAdj == null)
        {
            adjList[GetIndex(v1)].FirstAdj = p;
        }
        else
        {
            p.Next = adjList[GetIndex(v1)].FirstAdj;
            adjList[GetIndex(v1)].FirstAdj = p;
        }

        p = new AdjListNode<T>(GetIndex(v1));

        if (adjList[GetIndex(v2)].FirstAdj == null)
        {
            adjList[GetIndex(v2)].FirstAdj = p;
        }
        else
        {
            p.Next = adjList[GetIndex(v2)].FirstAdj;
            adjList[GetIndex(v2)].FirstAdj = p;
        }
    }

    // 无向图的深度优先遍历算法
    public void DFS()
    {
        for (int i = 0; i < visited.Length; i++)
        {
            if (visited[i] == 0)
            {
                DFSAL(i);
            }
        }
    }

    // 从某个顶点出发进行深度优先遍历
    public void DFSAL(int i)
    {
        visited[i] = 1;
        AdjListNode<T> p = adjList[i].FirstAdj;
        while (p != null)
        {
            if (visited[p.Adjvex] == 0)
            {
                DFSAL(p.Adjvex);
            }
            p = p.Next;
        }
    }

    // 无向图的广度 优先遍历
    public void BFS()
    {
        for (int i = 0; i < visited.Length; i++)
        {
            if (visited[i] == 0)
            {
                BFSAL(i);
            }
        }
    }

    // 从某个顶点出发进行广度优先遍历
    public void BFSAL(int i)
    {
        visited[i] = 1;
        CSeqQueue<int> cq = new CSeqQueue<int>(visited.Length);
        cq.In(i);
        while (!cq.IsEmpty())
        {
            int k = cq.Out();
            AdjListNode<T> p = adjList[k].FirstAdj;
            while (p != null)
            {
                if (visited[p.Adjvex] == 0)
                {
                    visited[p.Adjvex] = 1;
                    cq.In(p.Adjvex);
                }
                p = p.Next;
            }
        }
    }
}
